Conventional Reed-Solomon and convolutional coding have been used together to correct both burst and random errors, respectively, in a continuous stream of convolved data bits. Conventional convolutional encoders use an interleaver to interleave code bits over a larger time period for translating uncorrectable burst errors into correctable random errors. However, in low bit energy to noise power spectral density Eb/No applications, conventional convolutional coding error correction often does not meet system required bit error rates (BER). One technique for improving error rates is to repeat the transmission of a channel bit several times. A bit is partitioned into several identical bits and transmitted. However, this bit partitioning disadvantageously increases the effective transmission rate and may not effectively improve the BER in low bit energy to noise power spectral density Eb/No applications.
In recent years, the newly developed turbo code method has been demonstrated to be a very powerful tool for forward error correction of corrupted data communicated across noisy data channels. Turbo coding can provide significant coding gain within a fraction of 1 dB from the theoretical Shannon limit. This coding gain presents a promising future for power limited communication systems, such as a satellite communication system. The turbo code can provide significant coding gain at low Eb/No. In comparison with the commonly used concatenated Reed-Solomon convolutional codes, an additional coding gain can be achieved. Transfer function bound techniques have been studied to analytically compute the upper bound of the BER performance of a parallel concatenated convolutional code with a maximum likelihood decoder based on a trellis diagram and uniform interleaving. It has been shown that the simulated turbo code performance merge to this bound asymptotically. Therefore, this bound has been used to indicate where the error floor of a turbo code is located.
Turbo coding is a block code process using a transmitting turbo encoder and a receiving turbo decoder. In the case of continuous data transmission, turbo coding requires that the data stream be packetized into blocks for processing an entire message by blocks of N data bits. The turbo encoder provides systematic data bits uk and includes a first and a second constituent convolutional recursive encoders respectively providing e1 and e2 outputs of code bits. The first encoder operates on the systematic data bits providing the e1 output of code bits. An encoder interleaver provides interleaved systematic data bits then fed into the second encoder. The second encoder operates on the interleaved data bits providing the e2 output of code bits. The data uk and code bits e1 and e2 are concurrently processed and communicated in blocks of digital bits.
The conditional probability that the constituent encoder generates a codeword of weight dc given an information sequence of weight i and block size N can be expressed as pc(dc.linevert split.i)=t(N,i,dc)/C(N,i), where C(N,i) is the number of combinations of N bits taken i at a time, and t(N,i,d) is the number of codewords of weight d, which is simply the coefficient of the term L.sup.N *I.sup.i *D.sup.d of the transfer function T(L,I,D) of the constituent code with * being multiplication. Based on the assumption of uniform interleaving, the conditional probability of having a turbo codeword with a total weight of d given an information sequence of weight i and block size N is p(d.linevert split.i)=p0(d0.linevert split.i)*pc1(d1.linevert split.i)*pc2(d2.linevert split.i) where d=d0+d1+d2 with d0 being the weight of the systematic fragment of the codeword, d1 and d2 being weights of the encoded fragments corresponding to the first and second constituent encoder, respectively. The term p0(d0.linevert split.i) is a delta function d(i,d0), and pc1(d1.linevert split.i) and pc2(d2.linevert split.i) are given by the pc(dc.linevert split.i) equation. Applying well-known union bound techniques, the probability of bit error Pb for turbo codes can be expressed by a Pb summation equation of Pb being less than the summation from i=1 to N of (i/N)*C(N,i)*Ed.linevert split.i[Q[sqrt(2*d*(Es/No))]], where the conditional expectation Ed.linevert split.i(.) is over the probability distribution function given by the p(d.linevert split.i) equation and Q(.) is the complementary Gaussian distribution function with zero mean and unit variance, sqrt is the square root function, Es=R*Eb with R being the code rate. Therefore, the structure of the constituent encoder provides the transfer function T(L,I,D) and, as a result, the asymptotic BER performance, which can be used to locate the error floor, can be evaluated.
The second interleaver for the second encoder is an essential device for the turbo code structure. The encoder interleaver is used to increase the minimum Hamming distance between code words represented by the state transitions within the trellis diagram. The longer the Hamming distance between adjacent code words, the larger an error must be to be uncorrectable. Without this second interleaver, the Hamming weight of the combined two code sequences, e1 and e2, is only doubled using two identical constituent encoders. With the code rate decreased, the effectiveness of using concatenation is diminished. However, by uniquely interleaving the information systematic sequence that generates the minimum Hamming weight, and generates an interleaved systematic input to the second constituent encoder, the Hamming weight of the second code sequence e2 can be higher than that of the first code sequence e1.
In order to prevent the processing of a block of information from affecting the processing of the next block, the turbo encoder needs to be flushed at the end of each block. Flushing is the process of entering respective sequences of input flushing bits into the constituent encoders so that the contents of the respective shift registers of the encoders become all zeros, to put the encoders in the zero state, at the end of this flushing process. Because the turbo code adopts the recursive convolutional encoders, entering consecutive K-1 zero bits, where K is the constraint length of the code, does not flush the encoder as it does for the conventional nonrecursive convolutional encoder. The flushing bits for the first encoder are not part of, but are appended to, the informational root systematic data sequence. A first series of systematic tail bits are fed into the first encoder to flush the first encoder to the zero state as the first encoder generates parity check tail bits, after which, a second series of flushing bits are fed into the second encoder to flush the second encoder to the zero state while generating second parity check tail bits. Flushing the second constituent encoder, in the conventional manner, is to insert m generated input flushing bits to clear the contents of the shift register to all zeros. At the end of this flushing process, the corresponding path on the trellis diagram terminates at the all-zero state for both encoders. The flushing bits are particularly generated to flush the encoders into the zero state.
The first encoder operates on the systematic data and systematic tail bits to provide the first code bits including the first parity check tail bits while the second encoder operates on an interleaved version of the systematic data bits only to provide the second code bits and then generates the second parity check tail bits as appended to the second code bits. At the end of the systematic sequence, a first series of flushing bits is generated and used to flush the first encoder to the zero state as the first encoder generates first parity check tail bits appended to the first code bits, and concurrently, the first set of flushing bits is appended to the systematic data sequence of data bits as systematic tail bits, while concurrently, a second set of generated flushing bits is used to flush the second encoder to the zero state generating the second parity check tail bits without interleaving or appending this second set of flushing bits. Flushing of the second constituent turbo encoder create a tail effect inherent in block turbo encoding and decoding. Flushing of the constituent encoders provides known ending zero states to which forward recursion ends and from which backward recursion begins when estimating the systematic data sequence during decoding. The second encoder provides the second parity check tail bits from the second series of flushing bits which, however, are not appended to the systematic data bits, and hence, the second encoder does not have parity check tail bits encoded from the systematic tail bits as does the first encoder. Therefore, a tail effect is created by a mismatch between the systematic tail bits and the second encoder parity check tail bits. This tail effect does not extend to the first encoder parity check tail bits that were encoded from the systematic tail bits. Consequently, the entire systematic data and tail bit sequence can be compared to the entire string of first code bits for data verification. However, only the root portion of the systematic data sequence can be compared to the root portion of the second code bits, and disadvantageously the second parity check tail bits can not be compared to the systematic tail bits for verification. This difference in verification capability results from the tail effect mismatch. Hence, and as a result of the flushing process, there is a difference between the two sets of flushing bits respectively for the first and second encoders. This tail effect mismatch exists between the first set of flushing systematic tail bits that flush the first encoder to the zero state and the second set of flushing tail bits that flush the second constituent encoder to the zero state. As a result of this tail effect mismatch, the decoder can not compare the systematic tail bits against the second parity check tail bits. Such tail effects are a factor causing the error floor in turbo coding. Flushing of both of the constituent encoders is conventional practice in the art to terminate the encoding process to the zero state, but with the resulting error floor from the tail effect mismatch. But, a benefit of flushing the encoders to the zero state is that the decoder can take advantage of such known information to assist in the decision-making process for determining the systematic data bits. Specifically, the backward recursion of the turbo decoding process can start from this known zero state with a probability of one.
Turbo coding operates on blocks of input data bits dk. The turbo encoder includes the first and second recursive encoders having respectively data inputs and interleaved data inputs for providing respective strings of code bits e1 and e2, and includes a data channel providing the systematic unaltered data bits u. The code bits and data bits are used as branch words extending between states used in a Viterbi search algorithm using a trellis state diagram. Each encoder includes an feedback shift register having a limited number of determined states. As data bits or interleaved data bits are fed into the shift register, the encoder jumps among the states depending on the input bits as the encoder generates code bits. The data bits and code bits define possible branchwords. The code bits and data bits are transmitted over a noisy channel creating errors in the received code and data bits. At the decoder, the states and transitional branch words can be depicted using a trellis diagram upon which a-posteriori probability algorithm is applied to determine state metric values throughout the trellis diagram, and therefore the most probable transitions between states which then determines the data bit and code bits which should have been received so as to enable correction of erroneously received code and data bits. The a-posteriori probability algorithm can be applied in both forward and backward recursions using soft metrics based on channel characteristics and a-priori probabilities of bits being zeros or ones. The encoders start in the zero state and are flushed at the end of the block of data bits to end in the zero state. The a-posteriori probability algorithm is thus applied to known starting and ending states, and, sets of state metrics between the starting and ending states can be computed based upon conventional metric computational algorithms.
While the information data sequence, denoted by u, is being fed into the first encoder, an encoded sequence of N code bits, denoted by e1, is generated accordingly. The flushing systematic tail bits for the first encoder are appended to the tail of data sequence u, and combined as part of the systematic sequence uk that is transmitted over the channel. The m=K-1 flushing tail bits are referred to as systematic tail bits, denoted by u*. Associated with these systematic tail bits, the first encoder generates m parity check tail bits, denoted by e1*, which are appended to the tail of the first encoded sequence e1. Along with the systematic sequence u;u* the first code sequence e1;e1* is transmitted over the channel. The input sequence to the second constituent encoder is the interleaved version of u, denoted by p(u). The second code bit e2 are generated from interleaved data p(u). During the process of flushing the second encoder, the tail bits e2* are appended to the second code bits, Hence, for each block of N information bits, there are three (N+m) block strings uk=u;u*, e1k=e1;e1*, and e2k=e2;e2* transmitted through the noisy communication channel.
The data structures of the input and output sequences for both constituent encoders may be plotted as paths on trellis diagrams. The data structures of the systematic and code sequences that are transmitted over a noisy channel are assumed to be corrupted. The redundancy of the code sequences offers additional information for correcting data bit errors. The output data structure for turbo encoder includes one set of systematic data bits uk and two sets of code bits e1k and e2k providing one set of received systematic data bit sequence Xk and two sets of received code sequences Y1k and Y2k.
A code rate is the ratio of the number of data bits to the number of transmitted channel symbols. Decreasing the code rate improves the BER performance. However, for a fixed data rate, decreasing the code rate increases the transmission symbol rates. Channels are bandwidth limited and therefore require limited transmission symbol rates. One way of not increasing the transmission symbol rate while achieving a low code rate performance is to puncture the transmitted symbols. Puncturing is the process of deleting a portion of the transmitted symbols and the puncturing process is characterized by a puncture pattern used by the turbo encoder. Upon receipt of the transmitted punctured code symbols, the turbo decoder implements a bit insertion process that is the inverse function of the puncturing process. Bit insertion requires dummy bits inserted into the received sequence according an insertion pattern as part of the turbo decoding process. The puncturing and corresponding bit insertion processes result in a modest degradation of the BER performance while decreasing the transmission symbol rate to be within the acceptable channel bandwidth. Hence, puncturing and bit insertion processes are desirable in bandwidth limited applications.
The turbo decoder receives digital bits through a noisy channel typically communicating modulated analog signals. The noisy channel may corrupt the transmitted bits uk, e1k and e2k. Typically, a received voltage signal is demodulated into a voltage level and is then assigned a probability based on noisy channel characteristics and bit bias information for translating the received analog signals into digital bits. A communication channel has inherent noise characteristics. Bias information is used to describe the a-priori probability of a bit being a zero or a one. The bias information and the channel noise probability density function combine to provide channel a-posteriori probability estimations. The received digital bits include received systematic data bits Xk corresponding to the transmitted data bits uk, and received first and second code bits Y1k and Y2k corresponding to transmitted first code bits e1k and the second code bits e2k code bits, respectively. An information data bit is associated with a probability of being a zero or a one. Upon reception, the information bit has an initial a-priori probability. The bit has an a-priori probability of being a one or a zero for the received soft signal to provide a data bit estimate, and for computing a posteriori bias information.
The turbo decoder includes first and second a-posteriori probability (APP) decoders, a first decoder interleaver, a second decoder interleaver, an output deinterleaver, a feed back deinterleaver, and a hard limiter. These APP decoders and deinterleavers are connected for providing inverse functions of the encoders and encoder interleaver. The first and second APP decoders operate in the logarithmic domain. The APP decoders compute a-posteriori probabilities of the digital bits. The X and Y1 inputs have the same systematic order and are both inputted into the first APP decoder providing a first APP output in systematic order. The Y2 input is in an interleaved order by virtue of the encoder interleaver. The first APP decoder output is fed into a first decoder interleaver providing a first APP decoder interleaved output in interleaved order and the input X is also fed into the second decoder interleaver providing an X interleaved output in interleaved order. The output of the first APP decoder is an input to the first decoder interleaver providing an interleaved output to the second APP decoder. The second APP decoder provides, in turn, an interleaved bias information output that is deinterleaved by the feed back deinterleaver and fed back to the input of the first APP decoder, and provides an interleaved bit estimate output that is fed to the hard limiter that translates bit estimates into hard zero and one bit values. Hence, the turbo decoder includes a turbo feedback loop configuration for feeding back updated bias information. The output of the first APP decoder is a series of a-posteriori bias information, that is, a bias measurement of X based upon Y1. The X interleaved output, the first APP decoder interleaver output, and the Y2 input, all in interleaved order are fed into a second a-posteriori probability decoder providing the second APP decoder bias and bit estimate outputs in the interleaved order. One of the second APP decoder outputs is a refined APP metric output that is fed into the feedback loop deinterleaver for translating the second APP decoder bias output into systematic order for feed back into the first APP decoder. The feedback metric output and the first APP decoder metric output are a measure of the probability of the data X bits being ones or zeros. The second APP decoder provides bias information as a metric output for feed back and provides the estimate output that is not fed back to provide an estimate of the bit values. The second APP decoder estimate output is not fed back because it includes the first APP decoder metric output which should not influence the processing of the first APP decoder. The first and second APP decoder independently provides repetitive estimations for respective processing interactions.
At the end of the last iteration of the feedback loop turbo processing through the turbo decoder, the second APP decoder estimate output is fed into the output deinterleaver for generating an estimate output in systematic order for processing through the hard limiter for translating the estimates into hard data bit values. The second APP decoder provides an estimate of the systematic data X only at the last iteration. For each iteration, the second APP decoder provides a feedback bias metric output that is fed back into the first APP decoder. The estimate output of the second APP decoder is a logarithmic likelihood ratio output. The estimate output, in systematic order, is fed into a hard limiter for translating bit logarithmic likelihood ratios into zero and one bits of blocks of systematic data bits.
Each APP decoder performs branch and state metric computation during the forward recursion and backward recursion. The process of the forward recursion in the first and second APP decoders starts at the all-zero state with a probability of one, because the first and second encoder is always initialized at the all-zero state. The backward recursion in the first and second APP decoders also always starts from the all-zero state with a probability of one, because the first or second encoder always terminates at the all-zero state. At the end of the forward and backward recursions for each iteration, the first and second decoders perform logarithmic likelihood function calculation to provide the first and second decoder bias outputs as well as the second decoder estimate output.
The u*tail bits and e1* tail bits are the true matched pairs by virtue of encoding the u*tail bits in the first encoder so that the corresponding X* and Y1* tail bits can assist each other in determining decoded bits during the decoding. For example, if a parity check tail bit in e1* is severely corrupted and the corresponding systematic tail bit in u* is not, the use of X* can be used to correct the corruption of the Y1* bit, and vice versa. This is not true for the e2* and u* systematic tail bits because the e2* tail bits were not encoded in the second encoder from the u* systematic tail bits. During decoding using the e2* second parity check tail bits, arbitrary corresponding systematic tail bits u* may be used for error correction with a resulting inherent error floor. Specifically, the systematic tail bits X* cannot be used for decoding in the second APP decoder because the X* tail bits were not used to generate the Y2* tail bits. Using X* for decoding of the second parity check tail bits will cause unnecessary decoding errors at the tail portion resulting in the inherent error floor.
Therefore, after completing the decoding of the information root portion of Y2k, the systematic input X* is then effectively shut off with the X* systematic tail bit set to zero bit values. The lack of these systematic tail bits X* during the decoding of the second code bits Y2 limits the ability to correct the corruption of Y2* parity check tail bits and thereby limits the accuracy of the bit estimates creating the error floor. As such, decoding errors likely will exist at the tail in the event that Y2* is corrupted. Such errors may then propagate to the information root portion of the systematic sequence Xk. Although these errors may be corrected by the first APP decoder in subsequent iterations, the effect of these errors are continuously injected into the decoding process from one iteration to another.
The turbo code requires that the first and second encoders be flushed at the end of the information sequence. However, flushing the second constituent encoder results in a tail effect, with a mismatch between the second encoder parity check tail bits and the systematic tail bits. This mismatched tail effect of the conventional turbo decoders causes the two trellis paths of highest probability in the forward and backward recursions of the second APP decoder to not merge together at the tail portion of a block. Forward recursions may end at non zero states with the highest probability and yet backward recursions must start at the all zero states with a probability of one because the second encoder was flushed to the zero state resulting in a mismatch between the forward and backward recursions. Mismatches between forward and backward recursions is processed in the second APP decoder. When the second APP decoder decodes the k-th bit based on the likelihood function, which depends on forward metrics, backward metrics, and the branch metric at bit time k, this mismatch will cause the decision to wander between the forward and backward recursion paths from one iteration to another. Such instability creates some decoding errors in the rear section of the root data portion. This tail effect limits the ability of the decoder to correct error and hence establishes an inherent error floor during turbo decoding. These and other disadvantages are solved or reduced using the invention.